import common.ListNode;

public class Test3 {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if(head == null || head.next == null) {
            return head;
        }
        // 1. 计算链表的长度
        int count = 0;
        ListNode cur = head;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        // 2. 计算可以分成几个组
        int indexCount = count / k;
        // 将每一组进行反转并添加到原链表中
        // 3. 先创建一个新的头节点，保证所有的反转方式都一致
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        // 4. 定义需要用到的所有节点
        //    开始位置
        cur = newHead;
        // 5. 执行反转操作
        //    需要反转几组
        // 记录每一组反转后的尾节点
        ListNode oldNode = null;
        // 定义 curNext
        ListNode curNext = cur.next;
        for(int i = 0; i < indexCount; i++) {
            //  中间头节点
            ListNode tmpHead = null;
            // 记录上一组的最后一个节点，即此时的 cur 节点
            ListNode LastNode = cur;
            // 设置 oldNode，表示这一组反转后的最后一个节点
            oldNode = curNext;
            //  每一组需要反转的节点个数
            for(int j = 0; j < k; j++) {
                ListNode tmp = curNext.next;
                curNext.next = tmpHead;
                tmpHead = curNext;
                curNext = tmp;
            }
            // 此时需要将上一组的最后一个节点的 next 进行赋值
            // 赋的值就是新反转的范围的头节点
            LastNode.next = tmpHead;
            cur = oldNode;
        }
        // 设置最后一组的尾节点的 next 值: curNext
        cur.next = curNext;
        return newHead.next;
    }
}